package homework;
//作业标题(2735)
//两个节点的最近公共祖先
//
//作业内容
//两个节点的最近公共祖先
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
public class h2735 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == p || root == q) return root;
        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
        if(leftTree != null && rightTree != null) return root;
        else if(leftTree != null) return leftTree;
        else return rightTree;
    }
}
